package solution1.demo.demo11;

import java.util.Arrays;

public class Solution {

    //1.最后一块石头的重量 II(0-1背包)
    public int lastStoneWeightII(int[] stones) {
        int len = stones.length;
        int sum = 0;
        for(int i = 0; i < len; i++) {
            sum += stones[i];
        }
        int[] dp = new int[1501];
        int target = sum / 2;
        for(int i = 0; i < len; i++) {
            for(int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }

    //2.零钱兑换II(完全背包)
    public int change(int amount, int[] coins) {
        //完全背包问题
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

//    //3.买卖股票的最佳时机(动态规划-持续状态)
//    public int maxProfit(int[] prices) {
//        //dp[i][0] 表示第 i 天不持有股票，dp[i][1] 表示第 i 天持有股票
//        int len = prices.length;
//        int[][] dp = new int[len][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for(int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
//        }
//        return dp[len - 1][0];
//    }

//    //4.买卖股票的最佳时机 II(动态规划-多次买卖)
//    public int maxProfit(int[] prices) {
//        //dp[i][0]表示第 i 天不持有股票, dp[i][1]表示第 i 天持有股票
//        int len = prices.length;
//        int[][] dp = new int[len][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for(int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//        }
//        return dp[len - 1][0];
//    }

    //买卖股票的最佳时机 III(动态规划-指定次数买卖)
    public int maxProfit(int[] prices) {
        //dp[i][0] 什么都不操作
        //dp[i][1] 第 i 天持有第一张股票
        //dp[i][2] 第 i 天卖出，不持有第一张股票
        //pd[i][3] 第 i 天持有第二张股票
        //dp[i][4] 第 i 天卖出，不持有二张股票
        int len = prices.length;
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i = 1; i < len; i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[len - 1][4];
    }

    //买卖股票的最佳时机 IV(动态规划-买卖 k 次)
    public int maxProfit(int k, int[] prices) {
        int ans = 2 * k + 1;
        int len = prices.length;
        int[][] dp = new int[len][ans];
        //初始化
        for(int i = 0; i < ans; i++) {
            if(i % 2 == 1) {
                dp[0][i] = -prices[0];
            }
        }
        //递推
        for(int i = 1; i < len; i++) {
            dp[i][0] = dp[i - 1][0];
            for(int j = 1; j < ans; j++) {
                if(j % 2 == 1) { //持有股票
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }
        return dp[len - 1][ans - 1];
    }


    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        //寻找基准
        int point = fundPoint(arr, left, right);
        quick(arr, left, point - 1);
        quick(arr, point + 1, right);
    }

    private int fundPoint(int[] arr, int start, int end) {
        int key = arr[start];
        while(start < end) {
            while(start < end && key <= arr[end]) {
                end--;
            }
            arr[start] = arr[end];
            while(start < end && key >= arr[start]) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = key;
        return start;
    }

}

class Main {
    public static void main(String[] args) {
        int[] arr = {3,3,1,5,5,2};
        Solution solution = new Solution();
        solution.quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}